/**
 * Author: Brent Myers
 * Time-stamp: <2008-07-23 12:38:28 bam>
 * 
 * Linear Probing Hashtable Component
 * 
 */

#ifndef _LINEAR_PROBE_H_
#define _LINEAR_PROBE_H_

#include <utility>
#include <vector>

using std::pair;
using std::vector;

namespace genhash
{

struct HashtableFullException
{
	HashtableFullException() {}
	~HashtableFullException() {}
};

template <class Config_>
class LinearProbe
{
public:
	typedef Config_ Config;
	
	typedef typename Config::KeyType key_type;
	typedef typename Config::DataType data_type;
	typedef pair<key_type, data_type> value_type;

	typedef typename Config::HashFn hasher;

	typedef vector<value_type> BucketVector;
   	typedef vector<bool> UsedVector;

	typedef typename BucketVector::iterator iterator;

public:

	LinearProbe()
		: buckets(Config::max_size)
		, used(Config::max_size)
	{
	}

	~LinearProbe()
	{
	}


	iterator begin()
	{
		return buckets.begin();
	}

	iterator end()
	{
		return buckets.end();
	}

	size_t size() const
	{
		return buckets.size();
	}

	size_t max_size() const
	{
		return Config::max_size;
	}

	bool empty() const
	{
		return buckets.empty();
	}


	/**
	 * insert
	 */
	pair<iterator, bool> insert(const value_type& x) 
	{ 
		size_t pos = hash_mod(x.first);
		if(used[pos])
		{
			if(buckets[pos].first == x.first)
			{
				return make_pair(buckets.begin() += pos, false);
			}
			else
			{
				pos = probe_insert(pos);
			}
		}

		buckets[pos] = x;
		used[pos] = true;
		return make_pair(buckets.begin() += pos, true);
	}


	/**
	 * find
	 */	
	iterator find(const key_type& k)
	{
		size_t pos = hash_mod(k);
		if(used[pos])
		{
			if(buckets[pos].first == k)
			{
				return buckets.begin() += pos;
			}
			else
			{
				return probe_find(pos, k);
			}
		}
		else
		{
			return buckets.end();
		}
	}


private:

	/**
	 * hash and mod by the size
	 */
	size_t hash_mod(const key_type& k)
	{
		return hash(k);
	}

	/**
	 * probe for a place to insert or throw
	 */
	size_t probe_insert(const size_t start)
	{
		for(size_t i = start; i < max_size(); ++i)
		{
			if(!used[i])
			{
				return i;
			}
		}
		
		for(size_t i = 0; i < start; ++i)
		{
			if(!used[i])
			{
				return i;
			}
	   	}
		throw HashtableFullException();
	}
	
    /**
	 * find the element
	 */
	iterator probe_find(const size_t start, const key_type& k)
	{
		for(size_t i = start; i < max_size(); ++i)
		{
			if(buckets[i].first == k)
			{
				return buckets.begin() + i;
			}
		}
		
		for(size_t i = 0; i < start; ++i)
		{
			if(buckets[i].first == k)
			{
				return buckets.begin() + i;
			}
	   	}

		return buckets.end();
	}

	BucketVector buckets;

	UsedVector used;

	hasher hash;
	
};

}

#endif //_LINEAR_PROBE_H_
